/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * @author zhong
 *
 */
public class PyramidTransitionMatrix {
	/**
	 * ，增加预先判断同一行每个相邻对是否可能组成，312ms->22ms
	 * 
	 * @param bottom
	 * @param allowed
	 * @return
	 */
	public boolean pyramidTransition(String bottom, List<String> allowed) {
		HashMap<String, HashSet<Character>> allowMap = new HashMap<>();
		for (String string : allowed) {
			String key = string.substring(0, 2);
			if (!allowMap.containsKey(key)) {
				allowMap.put(key, new HashSet<>());
			}
			allowMap.get(key).add(string.charAt(2));
		}
		return can(bottom, allowMap);
	}

	HashMap<String, Boolean> meMap = new HashMap<>();

	private boolean can(String bottom, HashMap<String, HashSet<Character>> allowMap) {
		if (meMap.containsKey(bottom)) {
			return meMap.get(bottom);
		}
		if (bottom.length() == 2) {
			if (allowMap.containsKey(bottom)) {
				meMap.put(bottom, true);
				return true;
			} else {
				meMap.put(bottom, false);
				return false;
			}
		}
		// 预先检查每两个是否有可能
		for (int i = 0; i < bottom.length() - 1; i++) {
			String sub = bottom.substring(i, i + 2);
			if (!allowMap.containsKey(sub)) {
				meMap.put(bottom, false);
				return false;
			}
		}
		boolean res = helper(bottom, new StringBuilder(), 0, allowMap);
		meMap.put(bottom, res);
		return res;
	}

	/**
	 * 构造一行字符串
	 * 
	 * @param bottom
	 * @param next
	 * @param i
	 * @param allowMap
	 * @return
	 */
	public boolean helper(String bottom, StringBuilder next, int i, HashMap<String, HashSet<Character>> allowMap) {
		if (i == bottom.length() - 1) {// 如果构造的str已经到了最后，则看这一个字符串是否能
			return can(next.toString(), allowMap);
		}
		String sub = bottom.substring(i, i + 2);
		// if (!allowMap.containsKey(sub)) {
		// return false;
		// }
		HashSet<Character> characters = allowMap.get(sub);
		for (Character character : characters) {
			next.append(character);
			if (helper(bottom, next, i + 1, allowMap)) {
				return true;
			}
			next.deleteCharAt(i);
		}
		return false;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String bottom = "DECFCEAABACG";
		String[] allowed = { "BGB", "BGC", "BGD", "BGE", "BGF", "BGG", "ABF", "AGE", "AGC", "CCD", "CCG", "CCF", "EGG",
				"CCC", "CCB", "FBE", "DCF", "DCD", "DCE", "DCC", "DCA", "AGG", "FGD", "FGE", "FGF", "FGG", "FGA", "FGB",
				"FGC", "EDB", "BFE", "BFD", "BCA", "GAD", "DBB", "DBE", "DBD", "DBG", "DBF", "FFG", "FFF", "FFA", "FDA",
				"GBD", "FDB", "FDE", "GBC", "BEA", "BEG", "BED", "BEE", "AEA", "AEC", "AEB", "AED", "AEF", "EEE", "DEB",
				"DEC", "EGA", "DEF", "DEG", "CEG", "CED", "CEC", "CEB", "CEA", "CCA", "BDB", "GDB", "GEC", "GEF", "GEE",
				"GED", "BDG", "FBG", "EGD", "BDD", "GCC", "GCB", "BDA", "GCD", "GCG", "DGC", "AFF", "AFG", "AFA", "AFB",
				"EBG", "ECD", "DDC", "DDB", "DDA", "DDF", "DDE", "DDD", "CBB", "CBC", "CBA", "ECA", "CBD", "CBE", "CBG",
				"FAA", "ACA", "ACG", "ACD", "BCE", "BCF", "BCG", "FDC", "BCB", "BCC", "DGF", "GBB", "EFB", "FDD", "ECG",
				"ECF", "ECE", "DGA", "ECC", "ECB", "DGD", "GGD", "CGA", "CGC", "CGB", "CGE", "FCB", "EFE", "GGE", "FCA",
				"GGG", "FCC", "GGA", "GGC", "FCG", "FEF", "FEG", "FED", "FEE", "CGD", "FEA", "BBF", "BBE", "BBC", "ADF",
				"ADD", "ADE", "ADB", "ADC", "DFE", "DFG", "DFA", "DFB", "CDD", "CDE", "CDF", "EDA", "CDA", "CDB", "EDE",
				"EDC", "FBC", "GDA", "FBA", "GDD", "GDF", "GDG", "AAE", "AAG", "AAF", "AAA", "AAB", "BAF", "BAG", "BAD",
				"BAB", "CAA", "EEG", "CAD", "DAD", "DAE", "DAF", "DAG", "DAA", "DAB", "DAC", "EAC", "EAE", "EAD", "EAG",
				"EAF", "EGE", "EEC", "FAB", "GAF", "GAE", "EEB", "GAC", "FAD", "FAE", "EFA", "ABA", "ABB", "GCF", "ABE",
				"DEE", "ABG", "EBD", "EBF", "FCF", "EBB", "EBC", "CFD", "CFB", "CFA", "GFC", "GFA", "GFF", "GFG",
				"GFD" };
		List<String> allowList = new ArrayList<>();
		for (String string : allowed) {
			allowList.add(string);
		}

		System.out.println(new PyramidTransitionMatrix().pyramidTransition(bottom, allowList));
	}

}
